#include "Heap.h"
#include <string.h>

void Swap(int* x,int* y)
{
    int z = *x;
    *x = *y;
    *y = z;
}

void Adjust_up(HPDataType* _a,int childi)
{
    int parenti = (childi - 1) / 2;//计算出父亲下标的
    while(childi > 0)//结束条件2，当新插入的数据成为根节点
    {
        if(_a[childi] < _a[parenti])//当父亲大于新插入的数据,需要调整
        {
            Swap(&_a[childi],&_a[parenti]);
            
            //更新孩子和父亲下标，继续向上调整
            childi = parenti;
            parenti = (childi - 1) / 2;
        }
        else
            break;//结束条件1，新插入的数据大于等于父亲时
    }
}


void Adjust_down(HPDataType* _a,int parenti,int len)
{
    int left = parenti * 2 + 1;//左孩子的下标
    while(parenti < len && left < len)//结束条件2：当没有孩子可以进行交换
    {
        if(left + 1 < len && _a[left] > _a[left + 1])//找出最小的孩子
        {
            left++;
        }

        if(_a[parenti] > _a[left])//如果父亲大于孩子，需要进行交换
        {
            Swap(&_a[left],&_a[parenti]);

            //更新下标
            parenti = left;
            left = parenti * 2 + 1;
        }
        else
            break;//结束条件1：父亲小于孩子
    }
}

//堆的打印
void HeapPrintf(Heap* hp)
{
    for(int i = 0; i < hp->_size; i++)
    {
        printf("%d ",hp->_a[i]);
    }
    printf("\n");
}

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
    assert(hp);
    hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
    if(hp->_a == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    hp->_capacity = n;
    hp->_size = n;

    memcpy(hp->_a,a,sizeof(HPDataType) * n);//将a的数据拷贝进去

    int len = n - 1;//最后一个数据的下标
    for(int i = ( len - 1) / 2; i >= 0; i--)//向下调整建堆
    {
        Adjust_down(hp->_a,i,n);
    }
}

// 堆的初始化
void HeapInit(Heap* hp)
{
    assert(hp);
    hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
    if(hp->_a == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    hp->_size = 0;
    hp->_capacity = 4;
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_capacity = 0;
    hp->_size = 0;
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if(hp->_size == hp->_capacity)//需要扩容
    {
        HPDataType* temp = (HPDataType*)realloc(hp->_a,sizeof(HPDataType) * 2 * hp->_capacity);
        if(temp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        hp->_capacity *= 2;
    }

    hp->_a[hp->_size] = x;
    Adjust_up(hp->_a,hp->_size);
    hp->_size++;
}

// 堆的删除
void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    if(hp->_size == 1)//只有一个数据时，没有必要交换和向下调整
    {
        hp->_size--;
    }
    else
    {
        Swap(&hp->_a[0],&hp->_a[hp->_size - 1]);//交换头部和尾部的数据
        hp->_size--;//删除数据
        Adjust_down(hp->_a,0,hp->_size);//向下调整
    }
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    return hp->_a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
    assert(hp);
    return hp->_size;
}

// 堆的判空
int HeapEmpty(Heap* hp)
{
    assert(hp);
    return hp->_size == 0;
}
